package william.string;

/**
 * @author ZhangShenao
 * @date 2024/3/2
 * @description <a href="https://leetcode.cn/problems/valid-palindrome/description/">...</a>
 */
public class Leetcode125_验证回文串 {
    /**
     * 采用指针对撞法
     * 同时从字符串的首、尾两端同时开始遍历,判断两个字符是否相等
     * 如果遇到数字字符,则直接比较
     * 如果遇到字母字符,则统一转换成小写后比较
     * 如果遇到非字母、数字字符,则跳过
     * <p>
     * 时间复杂度O(N) 只遍历字符串一次
     * 空间复杂度O(1)
     */
    public boolean isPalindrome(String s) {
        //边界条件校验
        if (s == null || s.isBlank()) {
            return true;
        }

        //指针对撞,从首、尾两端同时开始遍历
        int l = 0;
        int r = s.length() - 1;
        while (l < r) {
            char c1 = s.charAt(l);
            char c2 = s.charAt(r);

            //跳过非字母和数字字符
            if (!Character.isLetterOrDigit(c1)) {
                l++;
                continue;
            }
            if (!Character.isLetterOrDigit(c2)) {
                r--;
                continue;
            }

            //同时为数字,直接比较
            if (Character.isDigit(c1) && Character.isDigit(c2)) {
                if (c1 != c2) {
                    return false;
                }
                l++;
                r--;
                continue;
            }

            //同时为字母,统一转换成小写后比较
            if (Character.isLetter(c1) && Character.isLetter(c2)) {
                if (Character.toLowerCase(c1) != Character.toLowerCase(c2)) {
                    return false;
                }
                l++;
                r--;
                continue;
            }

            //一个为数字一个为字母,返回false
            return false;
        }

        //比较完成,返回true
        return true;
    }

}
